// 一个循环数组大小为n，知道是有序的，但不知道哪个方向有序，
// 也不知道起点在哪里，请你设计一个算法，找出数组里的最小值，
// 要求时间复杂度O(logn)，没达到不得分，且要求描述算法思想并实现。


// 真难啊
#include "stdio.h"

int find_minimum(int arr[], int n) {
    int left = 0;
    int right = n - 1;
    while (left < right) {
        int mid = (left + right)/2;
        if (arr[mid] < arr[right]) {
            right = mid;
        } else if (arr[mid] > arr[right]) {
            left = mid + 1;
        } else {
            right--;
        }
    }
    return arr[left];
}

void test(){
        int test_cases[][5] = {
        // 升序排列，起点在数组的第一个元素处
        {1, 2, 3, 4, 5},
        // 升序排列，起点在数组的最后一个元素处
        {5, 1, 2, 3, 4},
        // 降序排列，起点在数组的第一个元素处
        {5, 4, 3, 2, 1},
        // 降序排列，起点在数组的最后一个元素处
        {2, 3, 4, 5, 1},
        // 中间某个位置发生旋转，旋转点左侧为升序，右侧为升序
        {4, 5, 1, 2, 3},
        // 中间某个位置发生旋转，旋转点左侧为降序，右侧为降序
        {5, 4, 3, 7, 6},
        // 中间某个位置发生旋转，旋转点左侧为升序，右侧为降序
        {3, 4, 5, 9, 3},
    };

    int num_test_cases = sizeof(test_cases) / sizeof(test_cases[0]);
    for (int i = 0; i < num_test_cases; ++i) {
        int n = sizeof(test_cases[i]) / sizeof(test_cases[i][0]);
        printf("数组:");
        for (int j = 0; j < n; ++j) {
            printf(" %d", test_cases[i][j]);
        }
        printf("\n");
        printf("最小值: %d\n", find_minimum(test_cases[i], n));
    }
}

int main(){
    test();
    return 0;
}